planar graphs course

notes

given: a graph that is sparse under the removal of vertices or contraction of an edge (parallel edges are considered as one).

wanted: a mst in time.

for a general graph, we could achieve using kruskal's algorithm.

let be a tree of degree at most 3 with weighed vertices so that every vertex weighs at most 1/4, we can find in linear time an edge such that every component of weighs at most 3/4.

let a tree of degree with weights applied to vertices such that every vertex weighs at most 1/4. we can find in linear time an edge such that every component in weighs at most 3/4.

the orbits of a permutation are the equivalence classes under the equivalence relation where if there exists such that . here the exponent indicates -fold composition, so if one can get from to by some number of applications of .

here's the idea. suppose we start with an embedding of a graph in the plane. for each vertex, walk around the vertex counterclockwise and you will encounter edges in some order, ending up in the same place you started. the embedding thus defines a cyclic permutation (called a rotation) of the edges incident to the vertex. there is a sort of converse: given a rotation for each vertex, there is an embedding on some orientable surface that is consistent with those rotations.

for an edge-centric graph , an embedding of is a permutation of the set of darts whose orbits are exactly the parts of . thus assigns a cyclic permutation to each part of , i.e. each vertex. for each vertex , we define to be the cyclic permutation that is the restriction of to .

we define the ordered pair to be an embedded graph. to be consistent with the definitions of unembedded graphs, we define and . we also define . the underlying graph of an embedded graph is defined to be the (unembedded) graph . we may denote an embedded graph by .

our interpretation is that tells us the arrangement of darts counterclockwise around in the embedding. such an interpretation is useful in drawings of embedded graphs. an example of an embedded graph and its embedding is given in fig-planar-graph-1.

to define the faces of the embedded graph, we define another permutation of the set of darts by composing with : then the faces of the embedded graph are defined to be the orbits of . we typically denote by .

for some purposes, it is convenient to distinguish one face, and designate it as the infinite face. any face of the embedded graph can be chosen to be the infinite face, and this freedom is exploited in the design of some algorithms.

for some graph , the application of the permutation to an entry of gives us another entry that is connected to , as is the next vertex in the orbit notice that we have .

informally, a planar dual of , is a planar graph whose vertices are the faces of and whose edges correspond to the edges of , this is demonstrated in fig-graph-emb-1, a formal definition for the dual is given in def-embgraphdual.

for an embedded graph , the dual graph (or just dual) is defined to be the embedded graph . we typically denote the dual of as .

it is not immediately obvious why the faces of correspond to the vertices of , with some imagination one may come to that conclusion by first demonstrating it on concrete graphs, the formal proof of deals with vector spaces and is included .

a primal graph and its dual (the dashed lines represent the dual).

in relation to the dual, the original graph is called the primal graph (or just the primal). note that the vertices of are the faces of .

deleting a dart from a permutation of is obtaining the permutation of defined as follows. deleting an edge consists of deleting the two darts of (in either order).

the contraction of an edge in is equivalent to the deletion of an edge in . for an embedded graph , if is not a self-loop then the underlying graph of is the graph obtained from the underlying graph of by contracting .

for any face , of any embedded graph , the darts comprising are connected.

if and are connected in then they are connected in .

for any embedded graph , a set of darts forms a connected component of iff the same set forms a connected component in .

a graph is planar if it has a planar embedding.

we say that an embedding of a graph is planar if it satisfies euler's formula: , where is the number of nodes, is the number of arcs, is the number of faces, and is the number of connected components. in this case, we say is a planar embedded graph or plane graph.

let be a planar embedded graph. a nonempty set of darts forms a simple cycle in iff the set forms a simple cut in .

let and be the number of vertices, edges, and faces of an embedded graph. the euler characteristic of the embedding is . the genus of the embedding is the integer that satisfies the formula

an embedding is planar if its genus is 0.

for any face of any embedded graph , the darts comprising are connected.

Let and be darts of . where . suppose . we claim that is a walk in , which proves the lemma. for , we have . by definition of , , so and have the same head in . thus .

if and are connected in then they are connected in .

for any embedded graph , a set of darts forms a connected component of iff the same set forms a connected component in .

for a planar embedded graph in which every face has size at least three, , where is the number of edges and is the number of vertices.

let be a planar embedded graph, and let be an edge that is not a self-loop. then is a planar embedded graph.

let be a plane graph, if is a spanning tree of then the edges form a spanning tree of .

if is a spanning tree of a plane graph , we use to denote the spanning tree of whose edges are (by duality of spanning trees). we refer to as the dual spanning tree with respect to in .

the spanning tree of a graph, along with are called the interdigitating trees of the graph.

we say a planar embedded graph is triangulated if each face's boundary has at most three edges.

an example for triangulated planar graph.

the following definition is an edge-centric definition of graphs, in which edges are primary and vertices are defined in terms of edges.

for any finite set , a graph on is a pair where is a partition of the set , called the dart set of . that is, is a collection of disjoint, nonempty, mutually exhaustive subsets of . each subset is a vertex of . for any , the darts of are the pairs and , of which the primary dart of is . for brevity, we can write as and as .

the head of a dart is the block such that contains . the tail of is the head of . note that this isnt exactly synonymous with edge direction, an edge can be directed towards but we can have a dart whose head is (when we have ).

there is one seeming disadvantage: this definition of graphs does not permit the existence of isolated vertices, vertices with no incident edges. this disadvantage is mitigated by interpreting a subset of edges of a graph as a kind of subgraph.

define the bijection rev on darts by . for a dart , is called the reverse of .

the terminology dart reverse may be deceiving, consider the edges , their corresponding darts are , we have that but because .

Let be a graph. the dart space of is , the set of vectors a that assign a real number to each dart . for a vector in dart space and given a set of darts, denotes .

the vertex space of is . a vector of vertex space is called a vertex vector.

the arc space of is a vector subspace of the dart space, namely the set of vectors in the dart space that satisfy antisymmetry: a vector in arc space is called an arc vector.

for a dart , define to be the arc vector such that and for all darts such that and . we extend this notation to sets of darts: . formally, a vertex is the set of darts having as head, so where the sum is over those darts whose heads are .

for a graph , we denote by the dart-vertex incidence matrix, the matrix whose columns are the vectors . that is, has a row for each dart and a column for each vertex , and the entry is 1 if is the head of if is the tail of , and zero otherwise.

for a graph and an edge , the contraction of in is an operation that produces the graph , where

, and
the part of containing and the part of containing are merged (and is removed) to form a part .

the graph obtained from by contracting is denoted .

like deletions, the order of contractions of edges does not affect the result. for a set of edges, the graph obtained by contracting the edges of is denoted .

given a graph , the deletion of an edge results in the graph . the deletion of a vertex results in the graph where is equal to with any edges that were incident to removed. the deletion of a set of vertices or edges can be denoted by .

if and are such that every path in contains a vertex or an edge from , we say that separates the sets and in . we say that separates two vertices, if it separates the sets, , but , and that separates if separates some two vertices in . a separating set of vertices is a separator, we may also call a single vertex a separator if the set is a separator.

a vertex is a separation vertex in an undirected graph iff there exist two vertices such that every path between and goes through .

let be a planar embedding, and let be a number between 0 and 1. an assignment of nonnegative weights to the faces, vertices, or edges of is an -proper assignment if no element is assigned more than times the total weight. a subpartition of these elements is -balanced if, for each part, the sum of the weights of the elements of that part is at most times the total weight.

let be binary tree, and let be a -proper assignment of weights to nodes such that each nonleaf node is assigned at most one-fourth of the weight. there is an edge such that every tree in has at most three-fourths of the weight.

assume the total weight is 1. for each node , define let be a leafmost 3/4-heavy node with respect to . let be the children of . note that because its a binary tree. since but , we must have , so (because nonleaf nodes get at most one-fourth of the weight). for , let be the weight of descendants of . let . by choice of , . by choice of , this shows that choosing to be the edge satisfies the balance condition.

let be a plane graph. a simple cycle of defines a subpartition consisting of two parts, the strict interior and the strict exterior of the cycle. if the subpartition is -balanced, we say that is an -balanced cycle separator.

for any plane graph , -proper assignment of weights to faces, and spanning tree of such that the boundary of each face of has at most three nontree edges, there is a nontree edge such that the fundamental cycle of with respect to is a -balanced cycle separator for .

let be the interdigitating tree, the spanning tree of consisting of edges not in . the vertices of are faces of , and are therefore assigned weights. the property of ensures that has degree at most three. using lem-graph-sep-2, let be an edge separator in of vertex weight. by the fundamental-cut and fundamental cycle duality, the fundamental cut of in with respect to is a simple cut in (each side of which has weight at most three-fourths of the total) so it is, by the simple-cycle/simple-cut theorem, a simple cycle in that encloses between one-fourth and three-fourths of the weight.

there is a linear-time algorithm that, given a triangulated plane graph , a spanning tree of , and a -proper assignment of weights to faces, edges, and vertices, returns a non-tree edge such that the fundamental cycle of with respect to is a -balanced cycle separator for .

we can give a better balance guarantee if we separating just edge-weight:

there is a linear-time algorithm that, given a triangulated plane graph with a -proper assignment of weights to edges, and a spanning tree , returns a nontree edge such that the fundamental cycle of with respect to is a -balanced cycle separator for .

separators are extremely useful for divide-and-conquer algorithms. in order to ensure that we dont place too much weight on a single subgraph, we need to make sure that the separator we choose is balanced and isnt too big, this motivates the following theorems.

there is a linear-time algorithm that, for a plane graph and -proper assignment of weights to edges, returns subgraphs such that

is a partition of (but is it really a partition? because ),
the partition is -balanced, and
.

the subgraphs are called the pieces. the set of vertices common to the two subgraphs is called the vertex separator.

let denote the edge-weight assignment. assume for notational simplicity that the sum of edge weights is 1. the basic idea is to find a balanced fundamental-cycle separator, which might be too long, and shortcut it at small BFS levels. the algorithm adds artificial zero-weight edges to to triangulate it. then, it performs a breadth-first search of from some node . let be the breadth-first-search tree. let denote the set of vertices at level . following lem-graph-sep-3, the algorithm finds a -balanced fundamental-cycle separator with respect to . we partition the edges of into two sets and , so that contains all edges strictly enclosed by and contains all edges not enclosed by . the edges of are assigned to and in a way that makes the partition -balanced. such a partition exists because the weight assignment is -proper, and can be computed in linear time by assigning the edges of to until the total weight of is at least . let and denote the minimum and maximum level of a vertex of , respectively. for an integer , let denote , and let denote . let be the greatest integer satisfying:

if no such level exists, we set . let be the smallest integer satisfying:

if no such level exists, we set . since for any level , the sets of edges corresponding to and to are disjoint, at least one of , is true. it follows that each of the levels has greater than vertices. hence, the total number of vertices among these levels is greater than , so . let be the set of edges whose endpoints have level at most if , and the empty set if . let be the set of edges with at least one endpoint at level greater than if , and the empty set if . let , and let . it is immediate to verify that is a partition of the edges of . by choice of and , for we have . since is a balanced separator, for we have . for , if , then the algorithm sets and all other edges of . since , it follows that and . assume therefore that for . let be the minimum integer such that . then and , so . the algorithm sets and all other edges of . then and .

there is a linear-time algorithm that, for a plane graph and -proper assignment of weights to vertices, returns subgraphs such that

is a partition of ,
the subpartition of is -balanced, and
.

we sometimes may want a simple cycle separator, which the-graph-sep-1 doesnt guarantee (fundamental cycle doesnt guarantee a simple cycle separator, see fig-fund-cut-cycle), the following theorem addresses this:

there is a linear-time algorithm that, for any simple undirected triangulated plane graph and any -proper assignment of weights to faces, edges, and vertices, returns a -balanced cycle separator of size at most .

let be a connected undirected graph. assume that are subsets of such that , the partitioning into groups by removing edges or vertices that connect them is called a cut in , and if applied becomes a disconnected graph.

note that although we state that a cut partitions a graph into two groups , the subgraphs restricted to dont necessarily have to be connected, so a cut may result in more than two disconnected subgraphs, for otherwise we call it a simple cut (see fig-cut-1).

for a graph and a set of vertices of , we define to be the set of edges having one endpoint in and one endpoint not in . we say a set of edges of is a cut of if it has the form .

we define to be the set of arcs whose tails are in and whose heads are not in . note that is a subset of . a set of arcs of is a directed cut (a.k.a dicut) if it has the form .

the cut set of a cut in a graph is the set of edges whose endpoints each exist in a different subset of the vertices that would result from the cut: where are the vertex subsets after the cut

for a set of vertices of , we define to be the set of darts whose tails are in and whose heads are not in . note that has one dart for each edge in . we refer to as the dart boundary of in .

let be a graph, let be a connected component of , and let be a subset of the vertices of . we say a cut or a dart cut is a simple cut if is connected in and is connected in . (some authors have used the term bond for this concept.) note that a cut in is minimal among nonempty cuts iff it is a simple cut. any cut can be written as a disjoint union of simple cuts.

let be a graph, and let be a spanning forest of . for a tree edge , let be the connected component of that contains . for , let we call the fundamental cut of in with respect to .

let be a connected planar embedded graph with spanning tree and let be an edge of . then the darts of the fundamental cut of in with respect to are the same as the darts of the fundamental cycle of in with respect to .

the drawing in fig-fund-cut-cycle-duality demonstrates this idea concretely which may help intuition.

if is a path and , then the graph is called a cycle.

a cycle is a simple cycle if it has no repeated vertices except the beginning and the end.

a non-empty sequence of darts is a walk if the head of is the tail of for every . to be more specific, it is a -to- walk if is or the tail of and is or the head of . we define the successor of in to be and we define predecessor of to be . we may designate a walk to be a closed walk if the tail of is the head of , in which case we define the successor of to be and the predecesor of to be . we also refer to a closed walk as a tour.

a walk is called a path of darts if the darts are distinct, a cycle of darts if in addition it is a closed walk. a path/cycle of darts is called a path/cycle of arcs if each dart is of the form . it is called a path/cycle of edges if no edge is represented twice.

let be a graph, and let be a spanning forest of . for a dart of an nontree edge, there is a simple head( )-to-tail( ) path of darts in whose edges belong to . write so is a simple cycle of darts, called the fundamental cycle of with respect to . for an arc of , we define the fundamental cycle of to be the fundamental cycle of the primary dart .

let be a simple cycle of darts in a connected plane graph . let be an arbitrary face, designated the infinite face. we say the cycle encloses a face with respect to if where .

prove that the dual of a planar embedded graph is planar. in other words, if is a planar embedded graph, prove that satisfies euler's formula.

given the planar embedded graph , we need to show that is planar. let be the number of nodes, number of edges, number of faces and the number of connected components in , respectively, and let be their "counterparts" in . we have that for by def-planar-emb, we need to show that . we have (from class we know the number of nodes in the dual is equal to the number of faces in the primal) and for the same reason, we have because the dual's embedding is a permutation whose length is the same as that of the primal's embedding, albeit with the arcs reversed (by def-embgraphdual), (the number of connected components) remains the same by lem-graph-emb-2, this implies that Euler's formula would still hold for the dual because the total values on both sides of the equation remain the same.

rootward computation

give a linear time algorithm for the following:

input: a rooted tree with vertex weights .
output: a table subtree_weight giving, for each vertex , the total weight of vertices in the subtree of rooted at .

i assume the idea is that from (Philip N. Klein and Shay Mozes, 2024):

the idea is to use recursion where each node returns the weight of the subtree that it is the root of to its parent, so that by the time we are at the parent all we need to do is grab the sum of its children without having to go deeper.

this item extends the rootward computation concept from the previous problem. to solve it you will need to use the concepts of interdigitating trees, fundamental cycles and enclosure. give a linear-time algorithm for the following:

input: a planar embedded graph , and a rooted spanning tree of .
output: a table giving, for each nontree edge , the lowest common ancestor of and in .

by the definition of a fundamental cycle, for every nontree edge we have a corresponding fundamental cycle in , every such cycle without the edge is a subtree whose root is some node , if we can reproduce these cycles in linear time we can assign to each pair of nodes in the subtree the designated ancestor (which can also be done in linear time). we know only one such satisfactory subtree (and hence one ) exists because is a spanning tree which has to be acyclic and cannot contain 2 different paths between any 2 nodes. first we number the spanning tree nodes by their levels, giving them a rank in the tree, this can be done using bfs starting at the given root of the tree, the nodes on the same level of the tree should get the same number and the deeper we go the higher the number is, this is demonstrated in fig-planar-graphs-homework-1. to construct the cycles we can use the fact that is a spanning tree of the faces of , where we have that each face, except one, is accompanied by a non-tree edge of , and each one of those faces defines a common lowest ancestor for the vertices in the face, so we would simply iterate through the non-tree edges, find their corresponding simple cycles and within these cycles look for the vertex with the lowest level which we appoint as the the root of the subtree, then insert the proper solution into the "table of solutions", this is demonstrated in fig-planar-graphs-homework-1. to iterate through the cycles we apply a rootward routine to the interdigitating tree that starts at the vertex whose degree is highest in , at each vertex we check the reversals of the darts of of to get the vertices surrounding the face in and grab the vertex with the lowest level among those to be the highest ancestor for all of the vertices in the face, then at every higher vertex in we apply the same process but compare the level of ancestor we receive to the ancestors we received from the children of the vertex, and pick the one with the lowest level.

to get a better understanding of the concepts i also had to draw fig-planar-graphs-homework-2.

the end product is shown in fig-planar-graphs-homework-3.

there is a slight problem in fig-planar-graphs-homework-3, we should be iterating through all the darts of a vertex in the dual graph, not the darts restricted to the interdigitating tree.

the algorithm finds the least common ancestors in linear time.

part 2

in class we proved the fundamental cycle lemma for graphs with face weights, but then used a version of the lemma for graphs with edge weights. in this problem you will justify this version of the lemma. a weight assignment is -proper if no element weighs more than times the total weight.

prove that there is a linear-time algorithm that, given a triangulated connected plane graph , a spanning tree of , and a -proper assignment of weights to faces, edges, and vertices, returns a nontree edge such that the fundamental cycle of with respect to is a -balanced cycle separator for .

by the fundamental cycle lemma, if we have a -proper assignment to faces then there is some whose fundamental cycle with respect to is a -balanced cycle separator, and since we have a triangulated graph, we have that each face has at most 3 vertices and 3 edges, giving us a total of 7 weight assignments for each face (3+3+1), each of which is , as a result we have that the total assignments for each face amount to , which equals , which gives us the satisfactory property to be able to invoke the fundamental cycle lemma, giving us the desired -balanced cycle separator.

prove the same as item (a), but when the weight assignment is 1/4-proper. hint: add artificial edges and faces with appropriate weights.

the idea is to offload the weights from vertices and edges onto faces, so that we can simply use the previous lemma to show that the desired separator must exist. since the graph is triangulated, there are 3 possible cases for a face:

a face of size 1 (a self-loop) would receive 3 weight assigments, one for the face, one for the edge, and another for the vertex. we can turn it into a vertex with three non-intersecting self-loops, and offload the three assignment to the three faces.
a face with two edges, it would have 5 weight assignments in total, we add 4 non-intersecting darts from one vertex to another to turn divide the face into 5 smaller faces that each get a assignment.
a face with three edges and 7 weight assignments, we apply the same process with 6 new darts to divide the face into 7 smaller faces.

this is demonstrated in fig-planar-graphs-homework-4

we then invoke the fundamental cycle lemma on the modified graph to get that we have a -balanced cycle separator for the graph, this works because by modifying the faces in this matter we arent severely modifying the structure or changing other properties of the graph, and so it almost remains the same except for a few redundant edges.

part 3

slack costs: the notion of slack costs will be useful in various algorithms in this course. let be a directed graph with length assignment from the darts to the real numbers, such that the length of every cycle in with respect to is non-negative. let be an assignment from the vertices of to the real numbers. the slack cost (sometimes called slack length) of a dart is defined as .

let be a vertex. let be a vector such that, for each vertex , is the -to- distance in w.r.t. the lengths . prove that, for every dart in , the slack cost is non-negative.
show that if is a shortest -to- path w.r.t. lengths , then it is also a shortest -to- path w.r.t. slack costs . what is the difference between the length of w.r.t. and w.r.t. ?
let be a directed sparse graph with dart lengths (i.e., ). use the claims from parts (a) and (b) to compute the distance between every pair of vertices in in time.

to understand the problem better i sketched a little and demonstrated the ideas on some concrete examples:

if the dart is in a self-loop then it is trivially true: let be a self-loop on a vertex , we have and but cant be negative because forms its own cycle and we cant have negative cycles. proof for the first claim:

let be the shortest path between the nodes and , we have 2 possibilities: either the shortest path from to is , or is some other distinct path. if the case is the former then we have

and so the property holds. if we have a distinct path for , let it be such that (such a path has to exist because we have no negative cycles), we have , which means that .

proof for the second claim:

let be some (directed) path from the node to the node , the path will start from and never visit it again, because if there is a path from to that visits twice it means that there is negative cycle in the graph, it will also not visit except one time, where it ends, it will not visit any (for ) twice for the same reason, so we have that the darts on the path from to have to be distinct. for any path , we have

we have that , hence the slack cost of the path boils down to: the expression eq-planar-graphs-hw-2-1 is minimal when we have the smallest , and this is true by definition when the path is the shortest between and . we have is constant for any because and the distance from to wouldnt change no matter what path we pick, similarly we have that is constant for any because , and so the expression's value is only affected by when varies, and since this expression is minimal when the path is minimal (with respect to ), we know is minimal when is minimal.

proof for the third claim:

since gives us a function of the weights (cost with respect to ) that maintains a minimal cost for the minimal paths and gives us positive weights, we can use as the weights when looking for minimal paths, so we invoke dijkstra's algorithm times (once for each vertex) with as the weights of the edges, since dijkstra finds the distances from one vertex to all others, this will give us the distances for all pairs of vertices. dijkstra runs in time, but since we have that (the sparsity property), we have that dijkstra runs in time, so the algorithm runs in a total time of

part 4 (bonus problem)

this problem is another example for the use of separators. let be a directed planar graph with real arc weights. a negative cycle in is a cycle whose arc weights sum to a negative number. consider a negative cycle in that has the minimum number of edges. let denote the number of edges on this cycle. using separators, give an -time algorithm for finding . only describe the algorithm and analyze its running time. there is no need for a formal proof of correctness. you will need to use the bellman-ford algorithm for computing a shortest-path tree from a given source vertex in a graph with real edge weights. recall that this algorithm works in phases, where each phase relaxes all the edges of the graph, and, at the end of the 'th phase, the algorithm has correctly computed, for each vertex , the length of the shortest -to- path that uses at most edges.

i didnt solve this one, (tbh i barely tried..)

a alternating path is a path that begins with an unmatched vertex and whose edges belong alternately to the matching and not to the matching.

an augmenting path is an alternating path whose first and last vertices arent in the matching.

we know: we can find an augmenting path in ( if the graph is weighted and we want an augmenting path of maximal weight).

we know: let be a maximum matching of . if there is no augmenting path in in relation to , is a maximum matching of . if there exists such a path , then the matching received by improving on using is a maximal matching.

the algorithm is:

find a balanced separator with nodes,
find a maximum matching in each separated part of the graph (without the nodes of the separator),
add the nodes of the separator one after another and find an augmenting path at each step.

from the facts above the matching found at the end of the process is maximal.

the time complexity is , for , . by induction we get .

let be a connected triangulated undirected graph. let be a vertex of , and let be a face incident to . for a face of , define its level to be the minimum level of a vertex incident to . thus, , and all faces to which is incident is also 0. for an integer , let denote the set of faces of with level at least . let denote the set of connected components of the subgraph of induced by . we refer to a connected component as a level- component, and we define . with a slight abuse of notation we identify a connected component of , which is a subgraph of , with the set of vertices of (faces of ) that belong to . thus, when it is convenient, we regard as a subset of .

for any level and any component , is a simple cut.

a region of is an edge-induced subgraph of .

a division of is a collection of regions such that each edge is in atleast one region. a vertex is a boundary vertex of the division if it is in more than one region. a division is an -division if there are regions, and each region has at most vertices and boundary vertices.

a natural face of a region is a face of that is also a face of . a hole of is a face of that is not natural.

an -division with few holes is an -division in which

any edge of two regions is on a hole of each of them, and
every region has holes.

a decomposition tree for is a rooted tree in which each leaf is assigned a region of such that each edge of is represented in some region. for each node of the decomposition tree, the region corresponding to is the subgraph of that is the union of the regions assigned to descendants of .

a decomposition tree admits an -division with few holes if there is a set of nodes of whose corresponding regions form an -division of with few holes.

for a constant , there is an -time algorithm that, for any triangulated planar embedded graph , outputs a binary decomposition tree for that simultaneously admits an -division of with few holes for every .

since the input graph is assumed to be triangulated, it follows that, for every region of , every natural face is a triangle. the algorithm is invoked by calling the procedure , given in (Philip N. Klein and Shay Mozes, 2024 Algorithm 5.1). given a connected region with more than edges, and given a recursion-depth parameter , first triangulates each hole of by adding an artificial vertex and attaching it via artificial edges to each occurrence of a vertex on the boundary of the hole. let be the resulting graph. the vertices and edges that are not artificial are natural. next, the procedure uses the planar-cycle-separator algorithm to find a simple-cycle separator consisting of at most natural vertices, where is a constant and is the number of vertices of (which is equivalent to the number of natural vertices of ). depending on the current recursion depth , the cycle separates in a balanced way with respect to either vertices, boundary vertices, or holes. note that the cycle separator algorithm is invoked on , which has more than vertices since it also has some artificial vertices. however, its shown in (Philip N. Klein and Shay Mozes, 2024 lemma 5.10.4) that there are at most twelve artificial vertices, the bound of still holds for some choice of (since ). the number of artificial vertices on the separator does not matter in the analysis of . the cycle determines a bipartition of the faces of the triangulated graph , which in turn induces a bipartition of the natural faces of . for , let be the region consisting of the edges bounding the faces in , together with the edges of that are in (i.e., omitting the artificial edges added to triangulate the artificial faces).

If is connected then is connected and is connected.

#+begin_proof the procedure calls itself recursively on and , obtaining decomposition trees and , respectively. the procedure creates a new decomposition tree by creating a new root corresponding to the region and assigning as its children the roots of and .

it is shown in (Philip N. Klein and Shay Mozes, 2024 chapter 5.10.1 number of holes) how to take care of holes.

let be the number of vertices in the original input graph . consider the decomposition tree of produced by . each node corresponds to a region . we define , and to be the number of boundary vertices of . we will show that for any given , admits an -division of . the analysis consists of two phases. in the first phase ((Philip N. Klein and Shay Mozes, 2024 lemma 5.10.8)), we identify a set of regions for which the number of vertices is at most , and the average number of boundary vertices is . however, some of the individual regions in this set might have too many boundary vertices (since the number of vertices and boundary vertices do not necessarily decrease at the same rate). we show that each such region can be replaced with smaller regions in so that every region has boundary vertices, and the total number of regions remains ((Philip N. Klein and Shay Mozes, 2024 lemma 5.10.9)).

(taken from Philip N. Klein and Shay Mozes, 2024 chapter 5.10 computing a decomposition tree) #+end_proof

input: a directed planar embedded graph with a desginated infinite face , a vector assigning lengths to darts, and a shortest-path tree rooted at one of the vertices of .
output: a representation of the shortest-path trees rooted at the vertices on the boundary of .

our goal is to give an algorithm that solves this problem in time where is the number of vertices (assuming no parallel edges).

there is an obvious obstacle: each shortest-path tree consists of edges, so explicitly outputting one for each of the possibly many vertices on the boundary of could take far more than time. to resolve this difficulty, we use a simple implicit representation of the shortest-path trees. let be the cycle of darts forming the boundary of where is the root of the given shortest-path tree (see fig-mssp-4). for , let be the shortest-path tree rooted at . we assume that each shortest-path tree includes only finite-length darts. the algorithm will describe the changes required to transform into , the changes needed to transform into ,…, and the changes needed to transform into . we will show that the total number of changes is at most the number of finite-length darts of .

the basic unit of change in a rooted tree , called a pivot, consists of ejecting one dart and inserting another dart so that the result is again a rooted tree. a pivot is specified by the pair of darts. transforming from to consists of

a special pivot that ejects the dart whose head is (from fig-mssp-4), and inserts the dart (now is -rooted)) (this is shown in fig-mssp-1), and
a sequence of ordinary pivots each of which ejects a dart and inserts a dart with the same head.

for , the MSSP algorithm outputs the sequence of pivots that transform into . we shall show that the amortized time per pivot is . the number of special pivots is . we also show that the number of ordinary pivots is at most the number of finite-length darts. it follows that the running time is .

to faciliate the exposition we first consider the non-degenerate case, where shortest paths are unique.

let be a graph, let be a dart vector, and let be a dart. for a vertex , we say is -tight with respect to if is tight with respect to the from- distance vector with respect to .

there is a -rooted shortest-path tree containing iff is -tight.

note that our unique shortest-pathss assumption implies that a dart is -tight if and only if is in the shortest path tree rooted at .

let be a planar embedded graph with infinite face , and let be a dart vector. let be the cycle of darts forming the boundary of . for each dart , the set forms a consecutive subsequence of the cycle .

the number of pivots required to transform shortest-path tree into , summed over all , is at most the number of finite-length darts.

we also need to show how using specific data structures we can find the necessary pivots and apply them in an amortized time of per pivot. throughout the algorithm, the tree we construct will always be a shortest-path tree.

for each dart , there is at most one iteration such that .

by the consecutive-roots lemma, there is at most one integer such that is in but is not in .

is at most the number of darts.

we describe how to move from , the tree rooted at , to , the tree rooted at , while maintaining a shortest-path tree. consider , this is a shortest-path tree for , let denote the distance from to . to convert to a tree rooted at , we insert into the tree the dart and throw out the dart in whose head is . the tree we receive will not be a shortest-path tree for , but if we modify the length of the dart to be , it will become a shortest-path tree. this is demonstrated in fig-mssp-1. a procedure called in the algorithm consists of a loop, each iteration of which selects a dart to add to and a dart to remove from . we show later that setting up the loop takes time, the number of iterations is , and each iteration takes amortized time. the time for is therefore . summing over all and using cor-mssp-1, we infer that the total time for and therefore for MSSP is . in each iteration, the algorithm determines that a dart not in must be added to . it then pivots into , which means

removing from the dart whose head is and
adding to .

conceptually, is as follows. let denote the -to- distance in . to initialize, temporarily sets the cost of the dart to . it then performs a special pivot, removing from the dart whose head is , and inserting into . it then gradually increases the cost of to its original cost while performing ordinary pivots as necessary to maintain that is a shortest-path tree. after the initialization, the procedure uses a variable to represent the current modified cost of . the costs of other darts remain unmodified. let denote the vector of costs. that is, under these costs, the cost of the path in to a vertex is denoted . the vector is not represented explicitly by the algorithm; we use it in the analysis and proof of correctness. after initialization, the procedure repeats the following two steps until equals the original cost of :

increase until any further increase would result in some dart becoming tense with respect to and .
pivot into .

this operation is demonstrated in fig-mssp-3.

by having that the initial value of the dart in the special pivot is , its as if we never moved from to in terms of distances from to other nodes, so the tree will be a shortest-path tree still (with respect to both and ), but we need to gradually increase while conducting normal pivots.

throughout the execution, is a shortest-path tree with respect to the costs .

the algorithm pivots in a dart only if necessary, i.e. if continuing the shrinking or growing phase without pivoting in would result in not being a shortest-path tree, in particular if would become tense with respect to and . a dart is in danger of becoming tense only if its slack cost with respect to is decreasing.

how do we know which darts need to be inserted into and when? we check the length of every dart not in , how much longer the path is than ( denotes the path from the root to in ). this difference in length we call the slack of with respect to , and denote it by where denotes the length of the path : when we add to the cost of , we consider what happens to :

if and are descendants of in , the slack doesnt change,
if and arent descendants of in , the slack doesnt change,
if is a descendant of and isnt, the slack increases by ,
if isnt a descendant of and is a descendant of , the slack decreases by .

we shift into the tree when its slack becomes cost becomes 0. since is a shortest-path tree, the slack cost of every edge that isnt in isnt negative, thus it suffices to keep track of the edges whose tails are in the subtree of and whose heads are in the subtree of . those are exactly the edges in the fundamental cycle of with respect to . in other words, these are the edges in the path from the face to the face . all we have to do (if at all), is to track the slack costs of the edges in the path from to in , all those edges arent in , which means they are in . the slack of all of those edges decreases by when we increase the length of by , thus the first dart whose slack cost reaches 0 is the the dart with minimal slack cost, hence to apply a pivot we need to:

find the dart whose slack cost in minimal in the path from to in . let be the dart, and be its slack cost,
subtract from the slack cost of all the darts in (on the path from to ), add to the slack cost of all darts in (on the path from to ), an add to the length of the dart .
remove the edge of whose head is from and insert into .

this process needs to be applied as long as hasnt yet returned to its original cost.

we can build a data structure for mssp that answers queries from a boundary vertex to any other vertex in time, where is the length of the shortest path to the destination vertex.

in class we sketched how to solve the maximum matching problem in planar graphs using separators. we argued that the running time for any input graph is bounded by the recurrence: where is the number of vertices of and and are the number of vertices of the two parts of obtained by deleting the vertices of the separator. prove that . hint: use induction on . beware of using the big-oh notation too liberally…

we include the definition of :

we apply strong induction on , for the base step, consider or , the problem can be solved in constant time (no need to apply a divide-and-conquer approach because there's nothing to divide), we have trivially. assume for the induction hypothesis that for every we have (for some constant ), we apply the induction step:

which gives us the constant for which we have for any sufficiently large and this means by definition.

in class we mentioned that there are data structures that can support all the necessary operations for MSSP in time per operation. in this problem you will develop a simpler data structure that supports similar operations on sequences (i.e., on paths) instead of on trees. this will give you a feeling for how the data structure for trees may be constructed. we shall represent a sequence of numbers by storing the numbers in a balanced binary search tree, where element is considered less (in the tree order) than element if .

describe how to support the operations , which splits the sequence immediately after the 'th element, and which, given two sequences with a total of elements, returns a single sequence consisting of all the elements of followed by all the elements of . the running time should be , where is the total number of elements. you may use the standard BST operations split and join (make sure you understand how they are implemented in at least one specific balanced BST implementation, but you do not have to explain that in your answer). make sure to address the following issue: you cannot afford to store the index of each element explicitly since the indices of many elements are changed by the join operation.
describe how to also support in time the operation , which returns the 'th number in the sequence, and the operation , which, adds to the first elements of the sequence.
describe how to also support in time the operation , which reverses the order of the elements between indices and in the sequence.
(bonus 5 points) describe how to also support the operation , which returns the minimum number among the first elements in the sequence.

using AVL trees we can concatenate two trees in , search is also , which can be used to split a given sequence. let denote the BSTs corresponding to the sequences , respectively.

to implement we consider the following: the elements of should be placed before the elements of in the tree, so that for any , we have that in the tree, and more generally we need to have that according to the order of the tree, to accomplish this we "stitch" the two trees together in such a way that rebalancing the resulting tree isnt too expensive. note that the keys in arent the values themselves but rather the indicies, each node holds both an index and a value (among other potential metadata), for example the node corresponding to will have the value of , but its key in the tree will be the index , which means that the tree will be ordered according to the indicies of the sequence, but not necessarily the values, this allows us to place arbitrary values in the sequence but maintain the order that we like. the steps for are:

remove the rightmost node from as you would in any AVL tree (this node would have the biggest key in , due to the ordering property of AVL trees),
construct a new tree with the left child being the modified tree , and the right child being the tree ,
apply AVL rotations to as necessary as if we just inserted it into the tree.

we may have to apply rotations to the new root to get the tree to be balanced, this would still take time. this algorithm runs in . an example is demonstrated in fig-planar-graphs-homework-3-1.

to implement , we search for ( refers to the node whose key is ) as we would in a binary search tree, which takes , and while looking for , we store the first node that has an index bigger than that we encounter, call it , once we reach , we extract the subtree rooted at and apply a left rotation to to get its right child to become the parent of the subtree that was rooted at , then remove the left subtree that is now rooted at the node whose index was , this is demonstrated in fig-planar-graphs-homework-3-2. note that if we store the path we took to get from to during the search, splitting the tree would be a matter of pointer manipulation and would take constant time.

to implement we apply the same search routine and grab the element with key and return its value. to support we use to first identify the set of nodes that we need to operate on, but we cant apply the operation directly because that would take time that is linear in , we instead use a technique called lazy propagation. we place a special mark we call "to-add" (using node "metadata") on the root of the first split of the tree, and other marks named "dont-add" on the nodes where we make the green cuts shown in fig-planar-graphs-homework-3-2, the first mark will hold the value which will tell us that all values of the nodes of the subtree rooted at the marked node need to be increased by ( can be equal to or can be an accumulation of for subsequent calls to ). the latter marks called "dont-add" will tell us that the effect of the first mark ends at those nodes, so that we dont apply add to the entire subtree unnecessarily. this wont modify the values of the nodes directly, but rather would be handled upon a call to one of the functions or any other function that applies a search routine to the tree, the function that applies the seaerch routine needs to check if the node it visits are descendants of a marked node, and apply the addition if so, then it needs to propagate the mark to its children, unless one of them has the "dont-add" mark that stops the "to-add" mark of its parent. to support we use the same idea of lazy propagation where we mark nodes for reversal instead of for adding a constant , to apply the reversal we would rotate the positions of the children of a node that we visit, so that the right child becomes the left child, and the left child becomes the right child (we apply this operation whenever we visit a node that is marked for reversal during later traversal of the tree).

let be an -vertex planar graph with non-negative dart lengths. let and be two faces, and be a simple path from a vertex on to a vertex on . give an -time algorithm that returns a minimum length simple cycle that enclosess exactly one of and , and crosses at most once. you probably understand intuitively what is meant by saying a path crosses . here is a formal definition: we say dart enters a simple path from the left if is an internal vertex of , and if the orbit of induces the cycle , where is the dart of whose head is , and is the dart of whose tail is . enters from the right if the induced cycle is . we say dart emanates left (right) of a simple path if enters from the left (right). we say a path crosses if there is a subpath of that can be written as , where enters from the left (right), is a (possibly empty) subpath of , and emanates right (left) of . hints: this problem is related to MSSP. the following thought experiment is useful. think of the graph embedded on a piece of paper. what becomes of the path when you take a knife, make an incision along , and then pull apart both sides of the incision? You may assume that the representation of the primal tree at any time along the execution of the MSSP algorithm allows you to query the length of the path in from the root to any vertex in time.
let be an undirected connected planar graph with non-negative edge lengths. let and be two faces of . give an -time algorithm that finds the shortest cycle in that separates and .
for vertices , in an undirected graph with edge capacities, a minimum st-cut is a set of edges that separates and and whose sum of capacities is minimum. let , be two distinct vertices in an undirected connected planar graph with non-negative edge capacities. give an -time algorithm that returns a minimum st-cut in .

a matrix is totally monotone if for every such that , and , we also have .

a matrix is convex monge (concave monge) if for every such that , we have ( ). it is immediate that if is convex monge then it is totally monotone. it is also easy to see that the matrix obtained by transposing is also totally monotone.

we define the upper triangle of to be the elements of on or above the main diagonal. more precisely, the upper triangle of is the portion of . similarly, the lower triangle of consists of all the elements on or below the main diagonal of .

we will be interested in computing all column minima of a monge matrix . let denote the number of rows (or columns) of , and assume has the convex monge property. for a subset of the rows of , the lower envelope of the rows of is the real-valued function on the integers in defined by (the minima of each column restricted to rows ).

let be a convex monge matrix. for any subset of the rows of , the function is monotonically non-increasing.

suppose . then, for , . since is convex monge, . therefore, for , , so .

a breakpoint of is a pair of integers such that and (the row contains the minima of column but not ). for , we always consider to be a breakpoint of . for notational convenience we also consider the pair as a trivial breakpoint. if are the breakpoints of the lower envelope of , ordered such that , then the minimum elements in each column in the range is at row .

we focus our attention on finding the breakpoints of the lower envelope of , since, given the breakpoints, all column minima can be recovered in time. lem-sssp-1 suggests the following procedure for finding the breakpoints of the lower envelope of a convex monge matrix . the procedure maintains the lower envelope of an increasingly larger prefix of the rows of . initially consists of just the first row of , and the breakpoints of are just and . let be the non-trivial breakpoints of the lower envelope of the first rows of , ordered such that . note that, by lem-sssp-1, this implies . to obtain the breakpoints of the lower envelope of the first rows of , the procedure compares and for increasing values of , until it encounters an index such that . by lem-sssp-1, and by the definition of breakpoints, this implies that

for all , , and
for all , .

hence, the lower envelope of the first rows of consists of a suffix of the breakpoints of starting at plus, perhaps, a new breakpoint for some . the exact column where the new breakpoint occurs can be found by binary search for the largest column such that .

we summarize the procedure in the following theorem.

there exists a procedure that computes the breakpoints of the lower envelope of a -by- convex Monge matrix in time.

(taken from Philip N. Klein and Shay Mozes, 2024 chapter 8.1.2 finding all column minima of a monge matrix)

note that in the following text (and usually in graph theory), denotes .

we describe a linear-space, nearly linear-time algorithm that, given a directed planar graph with real positive and negative lengths, but no negative cycles, and given a vertex , computes single-source shortest paths from to all vertices of . if there is a negative cycle, the algorithm should identify it. using bellman-ford we can achieve a time complexity of , and hence for plane graphs. the algorithm we propose runs in , and the best algorithm today runs in . the algorithm triangulates by adding edges with sufficiently large length so that shortest paths are not affected. it then uses the planar-cycle-separator theorem to separate into two parts; an interior subgraph and an exterior subgraph . the edges and vertices of the cycle separator are the only ones that belong to both parts. the vertices of are called boundary vertices. since is a simple cycle, it forms the boundary of a single face both in and in . the dense distance graph of is the complete graph on , where for any the length of the arc is the length of the -to- path in . the dense distance graphs of its parts.

consider one of the subgraphs ( ). since all boundary vertices lie on the boundary of a single face of , there is a cyclic clockwise order on the vertices in (boundary vertices). let be the weighted incidence matrix of . that is, equals the -to- distance in . we define the upper triangle of to be the elements of on or above the main diagonal. more precisely, the upper triangle of is the portion of . similarly, the lower triangle of consists of all the elements on or below the main diagonal of .

for any four indices such that either and are all in 's upper triangle, or are all in 's lower triangle (i.e., either or ), the convex monge property holds:

(taken from Philip N. Klein and Shay Mozes, 2024 chapter 8.1 total monotonicity and the monge property)

consider the vertices of in the order they are shown in fig-sssp-2(a). we claim that . since we have a planar graph the meeting point of the edges is a vertex in the graph, the proof for the claim says that if the path is the shortest then it is either the same length as the path or shorter, and the same case applies to the path with the alternative path .

in the incidence matrix of , the entries as their occur in fig-sssp-2(a) and fig-sssp-2(b) are shown in fig-sssp-2(c), fig-sssp-2(d), respectively. the matrices we consider will not be monge but their upper and lower triangles will be. if the 4 points shown in the matrices are on the lower triangle as in fig-sssp-2(c) then the monge property holds.

we present the description of the algorithm for computing shortest paths in the presence of negative arc lengths and no negative length cycles. it consists of five stages. the first four stages alternate between working with negative lengths and working with only positive lengths. let be an arbitrary boundary vertex.

recursive call: the first stage recursively computes the distances from within for . the remaining stages use these distances in the computation of the distances in .
intra-part boundary-distances: for each graph , the algorithm uses the mssp algorithm to compute all distances in between boundary vertices. this takes time.
single-source inter-part boundary distances: the algorithm uses a fast implementation of bellman-ford in the dense distance graph of to compute the distances in from to all other boundary vertices. has vertices, so the number of iterations of Bellman-Ford is . each iteration consists of relaxing all the edges . because for each , the upper and lower triangles of each has the monge property, all of the edges can be relaxed in time. thus this step is implemented in time.
single-source inter-part distances: for each , the distances obtained in the previous stages are used, in a dijkstra computation, to compute the distances in from to all the vertices of . dijkstra's algorithm requires the lengths in to be non-negative, so the recursively computed distances are used as a consistent price vector. this stage takes time. (this stage can actually be implemented in . this however does not change the overall running time of the algorithm.)
rerooting single-source distances: the algorithm has obtained distances in from . in the last stage these distances are used as a consistent price vector to compute, again using dijkstra's algorithm, distances from in . this stage also requires time.

the algorithm is given in fig-sssp-alg.

the algorithm is also demonstrated in fig-sssp-1.

we describe how to efficiently compute the distances in from to all boundary vertices (line-sssp-1). the algorithm computes the from- distances in by computing the from- distances in the dense distance graph . for , the edge lengths of the dense distance grah of have already been computed and stored in in the previous step.

let be a directed graph with arbitrary arc lengths. let be a cycle separator in and let and be the external and internal parts of with respect to . let and be the all-pairs distances between vertices in in and in respectively. let be an arbitrary boundary vertex. there exists an algorithm that, given and , computes the from- distances in to all vertices of in time and space.

consider the bellman-ford algorithm on . there are vertices, so the number of iterations is . in iteration bellman-ford computes for every , the quantity , which is the length of a shortest -to- path consisting of at most edges of . the following procedure, describes this process in detail.

the correctness of follows from the fact that it is an implementation of the bellman-ford algorithm. to complete the proof it remains to show that can be implemented in time. the number of iterations in is . it therefore suffices to show how to implement line-sssp-2 in time. this is the crux of the algorithm. consider the natural clockwise order on the boundary vertices, and regard the tables , as square -by- matrices. the key observation is that line-sssp-2 can be implemented by computing all column minima of two matrices , such that the element of is , and then taking pairwise distances between vertices on a single face of . since stores the minimum distances of the two values obtained for each column, it can be decomposed, by lem-sssp-2, into an upper triangular matrix and a lower triangular matrix, both of whom are convex monge. next note that adding a constant to each row of a monge matrix preserves the Monge property. for or , implies

hence each matrix decomposes into a lower and an upper triangular convex Monge matrices. the algorithm can therefore find all column minima of each by finding all column minima of each of the two triangular matrices comprising . using the extension to triangular matrices, this can be done in time, as desired.

(taken from Philip N. Klein and Shay Mozes, 2024 chapter 8 shortest paths with negative lengths)

one usecase fr-dijkstra is for running it on a that was generated by mssp (but doesnt mssp generate shortest-path trees? yes, but with respect to a single subgraph inside the infinite face). notice that, like classical dijkstra, fr-dijkstra alone cannot handle negative weights.

we make use of the monge property as we do in sssp with bellman-ford to receive a lower complexity for dijkstra in a . given a plane graph divided into regions by a cycle separator . is the complete dense distance graph in whose vertices are those of . the length of some edge in is the distance from to in . let . a naive implementation would take . we can achieve (which isnt enough time to look at all edges of ). in dijkstra, a typical implementation of takes time because relaxation of an edge might induce an update to the heap. we will see that its possible to implement in time. we will use a divide-and-conquer approach as in sssp, but we will need a more involved coordination between the divisions because the correctness of dijkstra requires us to find the global minima (vertex with smallest distance) at each step.

to be able to implement and efficiently, the algorithm decomposes the dense distance graph into bipartite graphs. each complete graph is decomposed into complete bipartite graphs as follows. consider the sequence of vertices of according to their clockwise order on . the algorithm splits the vertices into two consecutive halves and , and adds the complete bipartite graph on and to the decomposition. next, it recurses on and on . since and are disjoint, and their size is reduced by a factor of two at each level of the recursion, each vertex of appears in bipartite subgraphs. let denote the set of all bipartite graphs in the decompositions of both 's. the total number of bipartite graphs is . the decomposition procedure can also be illustrated by considering the weighted incidence matrix of . while this matrix is not monge, the submatrices that correspond to bipartite graphs are monge.

let be the (weighted) incidence matrix of (also denoted or ). let be a graph in the decomposition of into bipartite graphs. the restriction of to the vertices of is monge.

we consider to be a bipartite graph with sides and . always acts on a vertex in and always returns a vertex in . this gives us that the distance matrix of is monge. considering more than two , the set of one can be the set for another . the idea is that we dont have to relax all edges of , it suffices to know to which vertex of the distance is minimal. we say that is the parent of if we store for every those for which we have applied of its children.

for (where < denotes clockwise order of vertices), if is the parent of then isnt the parent of .

the set of children of some is a consecutive subsequence of the vertices of . it is sufficient to store for each the endpoints of the interval of its children in . these intervals we store as triplets which we store in a binary search tree in lexicographic order for fast access. we also store for each its child for which (the distance of the edge to ) is minimal, which we call the representative of .

if are the children of , the identity of the child with the minimal distance depends on but not .

we exploit this, before running the algorithm, during the construction of , we build a data structure that for each returns the index the construction time of this data structure is the same as that for , the query time is . although there is a faster construction that exploits the monge property of . to support , we save the representatives in the heap so that in time we can find the vertex whose distance is minimal. we remove from , we divide the triplet whose representative is into the triplets , and insert into the representatives of these triplets. to apply , we find the triplet in that comes after . we iterate through the triplets in starting at until we find a triplet for which becomes the parent of all vertices in in the triplets between and (excluding ). we find where the boundary between the triplet of and the triplet of lies using a binary search between and . we find the representatives of the triplets that were updated, we insert them into and remove from the representatives of the triplets that were removed. we apply a symmetric process to the triplets preceding in . finding takes , inserting the new triplet of to takes . but we iterate through many triplets to get there and every one of them takes (finding it in and inserting its representative in ). this structure we call a monge heap. every vertex is in bipartite graphs, for every bipartite graph we have a monge heap that supports the operations , to use every bipartite graph contributes its minimal representative to the global queue of dijkstra. we have more than one copy of every vertex, and when using dijkstra different copies of the same vertex can appear in the global queue as the global minimum, but in dijkstra every vertex has to be appear exactly once as a global minimum. so we ignore any duplicated appearances of the same vertex in the global queue and only treat the first occurrence as the legitimate one (we simply discard the duplicated occurrences without doing anything).

every copy of every vertex appears as the mimima of the global queue at most once. hence the number of iterations is . each operation of , takes time, so that the total time complexity is .

we can extend fr-dijkstra usage in different ways. one being the ability to add any number of edges, up to , to the distance graph, even in a way that may violate the planarity of the graph, while still being able to run fr-dijkstra on it. for these new edges we can apply a relaxation as in classical dijkstra, or simply treat each new edge as a monge heap of its own with one vertex on each side (sides ). adding such edges will give us extra monge heaps but it is not a matter of concern ( ). another extension is running fr-dijkstra on an r-division. for an -division we have pieces and each piece has boundary vertices and vertices, so we have boundary vertices in total. take every piece that has too many boundary vertices, give its boundary vertices the weight 1 and weight 0 to the rest and then find a balanced separator. a similar process can be applied to faces or holes, by assigning a weight of 1 to each hole and finding a proper separator. we can run dijkstra on the dense distance graph of all boundary vertices of all divisions. (the explanation given before was a special case where , for simplification.) to get the dense distance graph of a region we start by running mssp with as the infinite face (this gives us the distances between all boundary vertices and the distance from any boundary vertex to any enclosed vertex or backwards), then on each hole of the region we run mssp where the infinite face is the hole itself and the graph is the parent region, this gives us the outter dense distance graph of a hole, we have a constant number of holes so a constant number of mssp runs. each mssp on each region takes time ( for the number of holes which is constant). and since we have total regions the total time complexity amounts to which simplifies to . the resulting has vertices and since theres edges in every region and we have regions we get a total of edges. then we can run fr-dijkstra on it in time (in fr-dijkstra, comes from dividing into bipartite graphs, comes from the global queue).

a region of is an edge-induced subgraph of .

a natural face of a region is a face of that is also a face of . a hole of is a face of that is not natural.

an -division with few holes is an -division in which

any edge of two regions is on a hole of each of them, and
every region has holes.

a decomposition tree admits an -division with few holes if there is a set of nodes of whose corresponding regions form an -division of with few holes.

If is connected then is connected and is connected.

it is shown in (Philip N. Klein and Shay Mozes, 2024 chapter 5.10.1 number of holes) how to take care of holes.

(taken from Philip N. Klein and Shay Mozes, 2024 chapter 5.10 computing a decomposition tree) #+end_proof

i substituted for (the original writing has the latter) because this way the notation aligns with that of fig-sssp-alg.

recall that in the shortest-paths with negative lengths algorithm we computed the distances in from a vertex on the separator to all other vertices of , and the distances in from to all vertices of . we then said that we can compute the distances in from to all vertices of by running dijkstra in with respect to the slack costs given by the price function and with the distances of the vertices of initialized to their distances from in , which are given by . i claim that doing this literally is incorrect.

give an example where initializing the vertices of to their values in , and running Dijkstra with slack costs w.r.t. the price function would yield incorrect results.
one way to overcome this problem is to add to arcs from to each vertex of with length corresponding to the -to- distance in . prove that even though these lengths can induce negative slack costs with respect to , running dijkstra's algorithm with respect to these slack costs on is correct. i.e., for every vertex of the distance computed is the true distance in minus . hint: recall that the correctness of dijkstra's algorithm can be established by showing that at the time a dart is relaxed, the distance label of has already been set to the correct -to- distance.
another way to resolve this problem is to (1) remove all arcs entering , (2) add the same arcs as in (b), and (3) set the price function where is a number larger than the sum of absolute values of all dart lengths and remains unchanged for all other vertices of . prove that (1) the distances after these changes are the same as distances in , and that (2) the new definition of makes it feasible (i.e., induces non-negative slack costs).

the problem mentioned in (a) is demonstrated below: the respective slack costs for the lengths would be:

the issue happens because we arent considering paths that branch out from into (or backwards) that may be shorter than any path enclosed in .
dijkstra would start by relaxing all edges from to every other vertex (red edges in the drawing), once the edges are relaxed the vertices of would have the distance computed for them where

would be negative if a shorter path exists outside , as we would have , but dijkstra would work anyway because those edges are relaxed first and other edges wont have negative costs, and being made smaller than it is wont change the outcome because the path from to whose distance is given by is already the shortest from to so there is no harm in decreasing its computed length if we only care about relative length results (in the shortest-path tree sense). note that because . since the issue described in (a) isnt present here (because all the shortest paths are now present in the graph passed to dijkstra a path can be made up of multiple ones that branch out from one to another and back). the correctness follows from the correctness of dijkstra, at any time step for an edge we would have is the length of the minimal path to , otherwise we would have missed some other simple path from to on the way to where , but this cant be possible because dijkstra grabs the vertex for which is smallest at each time step, the rest follows from the correctness of dijkstra. by a telescoping sum (lem-slack-cost-2) we obtain that the slack cost (and hence the distance computed by dijkstra) of a path from to is
for some dart where we have is positive because is a from- price vector in and so slack costs with respect to are non-negative (by lem-slack-cost-1). if we may have (for the new edges): let represent the "duplicated" edges of , we have (we can think of it as ,) which means that , hence the expression of the slack cost is always non-negative. the proof of correctness is similar to the one given in the previous part of the problem (but here we have that the slack costs are positive, which doesnt matter in our case): dijkstra starts by relaxing all outgoing edges of which include the new edges, and so for every vertex we will have , but was initialized to anyway so it wouldnt change, then as described in the previous part since every edge of any possible simple path that crosses is contained in (each path that isnt closed in is represented by an edge that we added), and since the slack costs are all positive and are given by the modified from- price function ("modified" refers to the fact that ), we know that dijkstra will return the correct shortest path trees, because adding to all path costs will not affect the shortest path tree. we have

which means that the actual cost of the path in from to some vertex can be reproduced by simply subtracting and from the respective slack cost.

in class we've described FR-dijkstra on the union of the dense distance graph of the interior and exterior of a single cycle separator . in this problem we will extend the use of FR-Dijkstra to a more general case.

assume you are given an -division of a plane graph with the additional property that the boundary of every region is a single simple cycle in (so it is a single simple face in ). knowing the MSSP algorithm, you compute the dense distance graph for each region. how can you extend/modify FR-dijkstra to compute shortest paths in between boundary vertices of this -division? what is the running time?
in reality, there might not be an -division with just one boundary cycle per region. assume you are given a region whose boundary is composed of two cycles, , and (so and are faces of ). consider the edges of the dense distance graph of that correspond to distances from vertices of to vertices of . on the one hand, this is a bipartite graph. on the other hand, when there are two cycles, the matrix corresponding to those edges is not monge (you may want to convince yourself of this). i claim that nonetheless it is possible to use a single monge heap to handle all these edges. the reason is that the only structural property we used to argue the correctness of monge heaps is that the parent relationship is non-crossing. argue that the parent relationship in this case is non-crossing (proof by picture is fine). what small change in the implementation of the monge heap is required? (explain in 2-3 sentences, no pseudocode required).
assuming two cycles is too optimistic as well. there exists an -division where the boundary vertices in each region lie on a constant number of faces (this constant can be made as small as six cycles, also called holes). use the claim from item (b) to show how to extend/modify FR-Dijkstra to compute shortest paths in between boundary vertices of such an -division? what is the running time?

by definition of -division, we have regions and each region has boundary vertices and encloses at most vertices. we need to find a dense distance graph for each region, and since each region has vertices this would take per region using MSSP. since we have regions, the total time complexity of running mssp in all regions is we then stitch together all of the DDG's that we found to construct a new whole dense distance graph that holds the shortest distance between any 2 vertices on the same face. since there are regions and vertices per region, we have boundary vertices and edges in total. we note that this graph doesnt hold the correct distances with respect to . we then execute the extended version of fr-dijkstra on the whole dense distance graph (the union we constructed), which would take and would give us a shortest-path tree for a vertex on the union of the dense distance graphs, giving us the distance from to any boundary vertex of any region in the graph. an example demonstration of some of these ideas is shown in fig-planar-graphs-hw5-4.

for a region with holes, we notice that we cannot have edges that violate the non-crossing parent relationship, as shown in fig-planar-graphs-hw5-5.

in this case, when constructing the mongeheap we need to run MSSP twice, once from the boundary of the hole ( is the infinite face), and a second time from the boundary of the region ( is the infinite face).

for the distances from one boundary vertex of to another, we use the result of MSSP on and construct monge heaps as usual.
for the distances from one boundary vertex of to another, we use the result of MSSP on and construct monge heaps as usual.
for the distances from to (and vice versa), we take the results from the MSSP on , these edges already form a bipartite graph, we construct from them a single monge heap.

we change the order of the vertices of the side such that the first vertex becomes the child of the first vertex in and then continue in a circular manner according to the order of the vertices of . this way we make sure that there are no intersections in the parent relationships.

we want to modify fr-dijkstra from (a) to make it work with a constant number of holes per region. in each region we apply MSSP to every hole of , this would require time for every since the number of holes is constant. we build monge heaps over the boundary vertices of every hole as we did in class. between every pair of holes over the same region we need to build a monge heap as in (b), it wouldnt violate the parenthood relationship as we have shown. we get monge heaps for each so it takes to run all MSSP's and receive monge heaps. we then run fr-dijkstra like in (a) in time.

all-pairs boundary-to-boundary distances: you are given an -division with a constant number of holes per region of a planar graph . show how to compute the distances (in the entire graph ) between every pair of boundary vertices in total time (the notation hides polynomial factors in ). you should use MSSP and FR-Dijkstra (you may rely on the generalized use of FR-Dijkstra that you developed in problem prb-planar-graphs-course-hw5-1).

in prb-planar-graphs-course-hw5-1 we saw that constructing the DDG's will take time using mssp for each face (or hole) and that running fr-dijkstra on the resulting graph takes . we start by running MSSP over all holes as described before, we then run sssp to get the distances from one vertex to all others in the graph which will then be used for a from- price vector because it gives us positive costs while maintaining the same shortest path trees. we can then run the extended version of fr-dijkstra for each vertex with the slack cost function of the from- cost vector, this gives us a shortest path tree for all vertices which we can place in a matrix and query in constant time. every execution of fr-dijkstra will take (dum-fr-dijk-1) but the total cost would be the cost of fr-dijkstra multilpied by (the total number of boundary vertices in the division), giving us a total time of for running fr-dijkstra, which would simplify to . the final running time is

let be a planar graph with positive and negative arc lengths and no negative length cycles. consider a complete recursive decomposition of into subgraphs using small balanced simple cycle separators. for each piece , let denote the boundary vertices of (i.e., vertices of that are neighbors in of vertices not in ). let denote . let be the all-pairs distances in between the vertices of . let be the all-pairs distances in between the vertices of . in this problem we will compute, for each piece in the recursive decomposition both and . you may assume for simplicity that the boundary nodes of every piece lie on a constant number of faces (holes) of .

explain how to compute for all in time.
consider a piece whose subpieces in are and . what is in terms of ?
assume you are given . describe how to compute and in time.
describe how to compute for all in total time.

we use a modified version of sssp that, instead of finding its own cycles separator, makes use of the recursive decomposition tree that we have already obtained for the division. the modified version of the algorithm has to store for every region that it comes across, the correctness of the distances in follows from the correctness of sssp and the fact that it takes negative costs into account. sssp takes time to run.

we have and , hence , or we can write . this isnt descriptive of the how could vary, hence the demonstration in fig-planar-graphs-hw5-1.

we start by running sssp from some arbitrary vertex in a similar manner to the way we did in sol-planar-graphs-course-hw5-2, so that instead of letting the algorithm find new separators we use the decomposition tree of the division that we already have for the graph. the sssp algorithm defines a slack price function for every region or hole , let it be denoted by , we use these price functions when running mssp or fr-dijkstra over any graph because they let us compute the correct shortest-path trees without having to worry about negative distances. without loss of generality, let be the region that has vertices shared with (in any case atleast one of has to satisfy this property, see fig-planar-graphs-hw5-1), in cases where is enclosed in (fig-planar-graphs-hw5-1(b,d)), we can obtain (they arent necessarily equal but later we use the latter to construct the former), and this union can be trivially constructed since we have both operands already. hence focusing on finding (red edges in fig-planar-graphs-hw5-2, different cases of enclosure of are shown) should be enough given that the same process could be applied to obtain if isnt enclosed in . the boundary of has vertices, if we were to apply mssp in where forms the infinite face it would take . but we can run mssp in with the price function and where form the infinite face, but we also need to take care of any holes that we may encounter (and we can assume there is a constant number of those) in the way we described in sol-planar-graphs-course-hw5-1 by multiple mssp executions, which would run in , this would give us the outter dense distance graph of restricted to the subgraph , which we denote . then for each vertex of , we run fr-dijkstra with the distance function on with the boundary of as the cycle separator, to find the shortest path tree rooted at , this takes time. given that we have and since we need to run it as many times as , this would take and would give a shortest path tree for every in the subgraph , hence essentially giving us . the time complexity would be .

we apply a recursive process, passing each we obtain at each piece to its subpieces , at each recursion call we apply the process described above to obtain for the subpiece we have arrived at, since this is a divide-and-conquer algorithm over balanced subgraphs and since the time complexity for each case is at worst, we get a total time complexity of .

in class we discussed a simple -division based family of distance oracles that require space and preprocessing time, and have query time for essentially any (the notation ignores polylogarithmic factors in ). we also gave an fr-dijkstra based distance oracle with space and preprocessing time, and query-time. note that the latter (which we shall refer to as oracle-a) is better than using the former roughly when . use -divisions and oracle-a (as a black box) to design a family of distance oracles with space and preprocessing time, and query time . for simplicity, you may assume that the boundary vertices in each region in the -division lie on a single face (i.e., no holes). hint: note that in the preprocessing step you can afford to run MSSP in time (rather than just time) for each region of the -division, so you can compute MSSP and the DDG both for and for .

we run mssp on every region where form the infinite face, once in and again in to get (like we do in sol-planar-graphs-course-hw5-3). this would require space per region using the mssp data structure which allows us to get the distance from any boundary vertex to another vertex within the region in time. in total this requires step time and space. for a query: to retrieve the distance between the nodes and we run fr-dijkstra over the DDG's of the region but we first add edges from to every vertex and from every vertex to , this amounts to which the extended version of fr-dijkstra can handle and it wouldnt change the time complexity. after running fr-dijkstra we get the distance from to any other boundary vertex in the graph, including (because we placed the direct edges), the execution of fr-dijkstra on takes time.

first (naive) approach:

we take a naive approach that is based on an -division. first compute an -division with regions, each with vertices and boundary vertices. compute all pair shortest paths between all boundary vertices (in all of ), which would take space because we have boundary vertices. if we use an -division with a constant number of holes, we can compute these distances in time using mssp for each region and (prb-planar-graphs-course-hw5-2). for a query of distance from to : let be the regions in the division that contain , respectively. compute the shortest distances from in ( , using the results of the mssp executions in each face), compute the shortest distances to in ( ), find the pair in time where return the smallest among and ( , which denotes the direct distance between the two, is defined only if ), such a query takes time, if the vertices are on the same face and there is a direct path between them.

second approach

prb-planar-graphs-course-hw5-1

third approach

we start with a planar embedded graph with nonnegative edge-lengths. since we are dealing with distances, we can assume no self-loops and no parallel edges. we can also assume that is triangulated, by adding infinite-length edges as needed to ensure that each face is a triangle. all efficient distance oracles for planar graphs rely in some way or another on a decomposition of the graph using separators. we consider a specific decomposition tree of which we refer to as a recursive decomposition of . the root of corresponds to , and the two children of each internal node are obtained by separating the region using a simple cycle separator . (the precise choices of will be specified later.) the region corresponding to is the subgraph of enclosed by , and is the subgraph of not strictly enclosed by . note that is a face of both and . the decomposition is complete if the leaf subgraphs are small enough according to some measure of graph size, i.e. for every leaf , for a constant .

we say a path crosses a simple cycle if contains both an edge strictly enclosed by and an edge not enclosed by .

consider a recursive decomposition of using simple cycle separators. let be a path in . let be nodes of . if crosses and then then crosses for some common ancestor of and . this is demonstrated in fig-dist-oracle-1.

it follows that

for any path , there is a unique rootmost node in such that crosses .

notice that in the decomposition tree of a recursive decomposition of a graph, we have that each leaf in the tree corresponds to a region in the final division of the graph. this can perhaps be seen for some some of the leaves in fig-dist-oracle-1.

let be the input graph. the algorithm computes a shortest path tree rooted at an arbitrary vertex of . it then uses fundamental cycle separators with respect to to obtain a complete recursive decomposition of the input graph . each separator in the decomposition is a fundamental cycle . note that consists of (1) a nontree edge , together with (2) the -to- path in , and (3) the -to- path in . this implies that there are two leafward paths such that every vertex on the separator lies on at least one of the paths (the least common ancestor lies on both). note that since is a shortest path tree, both leafward paths are shortest paths in .

second approach:

we present an oracle with nearly linear space that can answer distance queries exactly in time. let be a directed plane graph with non-negative arc lengths. the oracle consists of a complete recursive decomposition of using small simple cycle separators (as described in dum-dist-oracle-1). each vertex stores a pointer to a leaf node such that contains . for each node of other than the root , let denote the parent of . recall that the separator cycle is a face of the region . the oracle stores the MSSP data structure for the face in the region . in addition, it stores , the dense distance graph of in . this complete graph is represented by a weighted adjacency matrix. the MSSP data structure requires space and preprocessing time. since , storing requires space, and it can be computed in time from the MSSP data structure. total size of all regions corresponding to nodes at each level of is , and since has levels, the total size and construction time of the data structure are . we now describe how to answer a query for the distance from to . let and be leaf regions of such that and , respectively. if the algorithm computes in constant time the distance within the constant size region . let be the lowest common ancestor of and in . for each ancestor of that is not a leaf of ( is a leaf only when ), the query algorithm computes using the following lemma.

can be computed in time.

let and be children of in such that and . observe that any -to- path that is restricted to intersects . such a path can be decomposed into (i) a path in from to a vertex of , (ii) zero or more paths whose endpoints belong to , each of which is either in or in , and (iii) a path in from a vertex of to . the algorithm runs fr-dijkstra on the dense distance graph of with respect to , which consists of the two cliques and . it initializes the distance labels for FR-Dijkstra with the distances in from to the vertices of (which can be queried in time per distance from the MSSP data structure stored for ). since the number of vertices of each is , the running time of FR-Dijkstra is . thus, FR-Dijkstra outputs the distance in from to the vertices of . the algorithm then computes as note that the distance for any can be queried in time from the MSSP data structure stored for .

the algorithm returns the minimum found among all ancestors of . the running time is dominated by the invocation of FR-Dijkstra at the top level when , which takes , because .

let be an arc vector. we can interpret as a plan for transporting amounts of some commodity (e.g. oil) along darts of the graph. if for some dart then we think of units of the commodity being routed along dart d. because satisfies antisymmetry, in this case. for an arc vector and a dart vector , we may refer to as a flow assignment and refer to as a capacity assignment, in which case we say is capacity-respecting with respect to if , i.e. if every dart satisfies . meaning that capacity is an upper bound for flow. for a dart , we have and .

note that the values of are allowed to be negative. let be a flow assignment that is capacity-respecting with respect to , and suppose for some dart and some positive number . then , so by antisymmetry . thus a negative capacity can be interpreted as a lower bound on the reverse dart.

the (net) outflow of at a vertex is defined to be . this is the net amount of the commodity that leaves . we say satisfies conservation at if the net outflow at is zero.

an arc vector that satisfies conservation at every vertex belongs to the cycle space. a vector in the cycle space of is called a circulation of . we can interpret a circulation as a plan for transporting a commodity through the graph in such a way that no amount is created or consumed at any vertex. a vector in the cycle space of a graph is called a circulation in . let be a dart vector. suppose is a connected planar embedded graph, and let be one of the faces. a circulation can be represented as a linear combination:

or, more concisely, as , where is a vertex vector of . we refer to the coefficients as face potentials. for even more simplicity, we can write

again where is a function that assigns values to faces (face potentials). the notion of circulation is demonstrated in fig-flow-1. note that in eq-circul is a vector hence is also a vector multiplied by . also note that is still an arc vector, albeit in the dual graph.

we know by definition circulation corresponds to face prices, we show that the contrapositive is also true. let be a price function on faces. we want to show that defined in eq-flow-1 is a circulation. cosnider a vertex (fig-flow-3): this sum amounts to 0 because it telescopes out. hence we have that face prices also correspond to circulations.

according to our convention .

any circulation can be decomposed into a set of simple flow cycles. this is demonstrated in fig-flow-1.

let be a circulation of , and let be a price vector of such that . then the circulation is capacity-respecting with respect to iff is a consistent price vector in with respect to .

let be a connected plane graph, and let be a capacity function. there is a circulation in that is capacity-respecting with respect to iff the dual contains no cycle of darts whose length with respect to is negative.

given a capacity assignment and an arc vector , the residual capacity assignment is defined as .

for a circulation whose potential is , the residual capacity is

meaning that the residual capacity of with respect to the circulation is the slack cost of with respect to the price vector .

the following claim is from class, follows it is the related one from the textbook

if is the potential of a circulation , and induces non-negative slack costs then i.e. , or in other words, is capacity-respecting of iff induces non-negative slack costs.

let be a circulation of , and let be a price vector of such that . then the circulation is capacity-respecting with respect to iff is a consistent price vector in with respect to .

for every dart , therefore the left-hand side is nonnegative iff the right-hand side is nonnegative.

for nodes and , a capacity-respecting flow assigment is an st-flow if it satisfies conservation at every node except possibly and . the value of an st-flow is

for two st-flows and with the same value, the difference is a circulation.

finding the value of a flow corresponds to finding a minimum simple cut with (respect to capacity, i.e. with capacity being the cost function for edges), because we cannot have an st-flow with a value that is greater than sum of capacities of edges that separate the graphs into two disconnected subgraphs containing and .

max st-flow is the following problem: given a graph with a capacity assignment , and given vertices , compute an st-flow whose value is maximum. ordinarily the capacity assignment is assumed to be nonnegative. in a slight variant, -limited max st-flow, one is additionally given a number , and the goal is to compute an st-flow whose value is maximum subject to the value being at most . if is assigned an upper bound on the maximum value of an st-flow, e.g. the sum of capacities of the darts whose tail is , the limit has no effect. this shows that ordinary max-flow can be reduced to limited max-flow. (the reverse reduction is also not difficult.)

we assume non-negative capacities. given , let be some st-flow with value but isnt necessarily capacity-respecting (for example, for any edge that is on a path from to ). if isnt capacity-respecting, then in the residual graph we would have edges with negative capacity. find a circulation that respects the capacity by computing shortest paths in : meaning is an st-flow with value that respects the capacity . if we dont know , we apply a binary search on values up to where is the sum of all capacities, we find the value for which there are no negative cycles in . this takes time. note that this is a weakly-polynomial time complexity, meaning that it depends on the input itself, not its size. if and are on the same face, the algorithm is:

add edge from to whose capacity is ,
compute : the shortest distances from in ,
return : the restriction of to the original edges of .

is a circulation in . hence is an st-flow in . a better approach: we start by finding a shortest-path tree in whose root is some face that contains , denote it .

the distances in induce a circulation ,
apply flow in . now the slack costs with respect to are the residual capacities with respect to . all darts of are saturated (have residual capacity 0). let be the spanning tree of that contains darts that arent in , and whose root is in . the darts of arent saturated (because the lengths are uniform).

as long as is connected to in :

let the path in from to . all of its darts that have non-negative slack costs with respect to (which are exactly those that have non-negative residual capacity),
let be the dart of whose residual capacity or slack cost is minimal,
let the residual capacity or slack cost of ,
for each dart , increase by , decrease by , do this by flowing through ,
let be the dart of whose head is , remove from and from , insert into and into , these steps amount to a pivot of .

note that when inserting into its residual capacity is full because its reverse is saturated. the following invariants hold:

the flow is conserved (excluding and ) and is capacity-respecting.
an edge is in iff it isnt in .
the darts of are saturated.

the algorithm finishes when and arent connected in , i.e., the last pivot created a cycle in (when the red edge that we insert is from a vertex to its ancestor), this cycle corresponds to a cut that separates from and all of its darts are saturated, hence at that time is a maximal st-flow. the time complexity: this is similar to mssp, with the replacement of the separators of and . if we represent the tree using a dynamic tree, the tree using a parent list, we can apply every iteration of the loop in amortized time. whats left is to show that the number of iterations is equal to the number of pivots.

for a ground set , a carving of is a maximal non-crossing family of subsets of . by maximal, we mean that you cannot add any other subset of to .

a noncrossing family of sets forms a rooted forest under the subset relation. the forest corresponding to a carving is a rooted binary tree, i.e. it has a single root and each node has at most two children. to see that it is binary, suppose that some node has children , and . the set does not cross any descendant of or (it includes each of these sets) or (it is disjoint from this set) or any ancestor of (it is a subset of each of these sets) or any node that is neither an ancestor nor a descendant of (is disjoint from these sets). therefore is also noncrossing, contradicting the maximality of .

let be a graph. a carving of is called a carving-decomposition. the width of a carving-decomposition is . the carvingwidth of a graph is the minimum width over all carving-decompositions.

for each vertex of , the carving contains the singleton set . the corresponding cut includes all the edges incident to (not including self-loops). thus the width is at least the maximum degree of the graph. this somewhat limits the usefulness of carvingwidth.

let be a planar embedded graph of degree at most . let be a spanning tree of the dual , and suppose that every simple path in consists of at most edges. then has a carving-decomposition of width at most .

let be a graph. a carving of is called a branch-decomposition. the width of a branch-decomposition is , where is the set of vertices with some incident edge in and some incident edge not in .

for a graph and a vertex , we define the radius of with respect to to be the maximum vertex depth in a bfs tree rooted at r. that is, the radius is the maximum over vertices of the minimum size of an -to- path.

there is a linear-time algorithm that, given a planar embedded graph , returns a branch-decomposition whose width is at most where the radii are with respect to given vertices.